{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. _nb_repair:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Repair\n",
    "\n",
    "The repair operator is mostly problem-dependent. Most commonly, it is used to make sure the algorithm is only searching in the feasible space. It is applied after the offsprings have been reproduced. In the following, we are using the knapsack problem to demonstrate the repair operator in *pymoo*.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the well-known **Knapsack Problem**. In this problem, a knapsack has to be filled with items without violating the maximum weight constraint. Each item $j$ has a value $b_j \\geq 0$  and a weight $w_j \\geq 0$ where $j \\in \\{1, .., m\\}$. The binary decision vector $z = (z_1, .., z_m)$ defines, if an item is picked or not. The aim is to maximize the profit $g(z)$:\n",
    "\n",
    "\\begin{eqnarray}\n",
    "max & & g(z) \\\\[2mm] \\notag \n",
    "\\text{s.t.} & & \\sum_{j=1}^m z_j \\, w_j \\leq Q \\\\[1mm] \\notag \n",
    "& & z = (z_1, .., z_m) \\in \\mathbb{B}^m \\\\[1mm] \\notag \n",
    "g(z) & = & \\sum_{j=1}^{m}  z_j \\, b_j \\\\[2mm] \\notag \n",
    "\\end{eqnarray}\n",
    "\n",
    "\n",
    "A simple GA will have some infeasible evaluations in the beginning and then concentrate on the infeasible space.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.operators.crossover.hux import HUX\n",
    "from pymoo.operators.mutation.bitflip import BitflipMutation\n",
    "from pymoo.operators.sampling.rnd import BinaryRandomSampling\n",
    "from pymoo.optimize import minimize\n",
    "from pymoo.algorithms.soo.nonconvex.ga import GA\n",
    "from pymoo.problems.single.knapsack import create_random_knapsack_problem\n",
    "\n",
    "problem = create_random_knapsack_problem(30)\n",
    "\n",
    "\n",
    "algorithm = GA(pop_size=200,\n",
    "               sampling=BinaryRandomSampling(),\n",
    "               crossover=HUX(),\n",
    "               mutation=BitflipMutation(),\n",
    "               eliminate_duplicates=True)\n",
    "\n",
    "\n",
    "res = minimize(problem,\n",
    "               algorithm,\n",
    "               termination=('n_gen', 10),\n",
    "               verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Because the constraint $\\sum_{j=1}^m z_j \\, w_j \\leq Q$ is fairly easy to satisfy. Therefore, we can make sure that this constraint is not violated by repairing the individual before evaluating the objective function.\n",
    "A repair class has to be defined, and the population is given as input. The repaired population has to be returned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from pymoo.core.repair import Repair\n",
    "\n",
    "\n",
    "class ConsiderMaximumWeightRepair(Repair):\n",
    "\n",
    "    def _do(self, problem, Z, **kwargs):\n",
    "        \n",
    "        # maximum capacity for the problem\n",
    "        Q = problem.C\n",
    "        \n",
    "        # the corresponding weight of each individual\n",
    "        weights = (Z * problem.W).sum(axis=1)\n",
    "        \n",
    "        # now repair each indvidiual i\n",
    "        for i in range(len(Z)):\n",
    "            \n",
    "            # the packing plan for i\n",
    "            z = Z[i]\n",
    "            \n",
    "            # while the maximum capacity violation holds\n",
    "            while weights[i] > Q:\n",
    "                \n",
    "                # randomly select an item currently picked\n",
    "                item_to_remove = np.random.choice(np.where(z)[0])\n",
    "                \n",
    "                # and remove it\n",
    "                z[item_to_remove] = False\n",
    "                \n",
    "                # adjust the weight\n",
    "                weights[i] -= problem.W[item_to_remove]\n",
    "          \n",
    "        return Z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "algorithm = GA(pop_size=200,\n",
    "               sampling=BinaryRandomSampling(),\n",
    "               crossover=HUX(),\n",
    "               mutation=BitflipMutation(),\n",
    "               repair=ConsiderMaximumWeightRepair(),\n",
    "               eliminate_duplicates=True)\n",
    "\n",
    "\n",
    "res = minimize(problem,\n",
    "               algorithm,\n",
    "               termination=('n_gen', 10),\n",
    "               verbose=True)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As demonstrated, the repair operator makes sure no infeasible solution is evaluated. Even though this example seems to be quite easy, the repair operator makes especially sense for more complex constraints where domain-specific knowledge is known."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
